/*
    XTU OJ: 1339
    by: fifth_light
*/

/*
    XTU OJ: 1279
    by: fifth_light
*/
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

char table[1000050] = {0};
int primes_len = 0;
int primes[400000] = {0};
char table2[1000050] = {0};
int results[1000050] = {0};

void prepare_table() {
    //printf("prepare\n");
    for (int i = 2; i <= 1001; i == 2 ? (i = 3) : (i += 2)) {
        for (int n = i; n < 1000050; n += i) {
            if (i != n) table[n] = 1;
        }
    }
    table[0] = 1;
    table[1] = 1;
    table[2] = 1;
    for (int i = 0; i < 1000050; i++) {
        if (table[i] == 0) {
            primes[primes_len++] = i;
            int sum = primes[primes_len - 2] + i;
            if (sum % 2 != 0) {
                continue;
            }
            int num = sum / 2;
            if (table[num] == 1) {
                table2[num] = 1;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < 1000050; i++) {
        if (table2[i] == 1) {
            res++;
        }
        results[i] = res;
    }
    //printf("final\n");
    //exit(0);
}

int prime_count(int start, int end) {
    if (table2[start] == 1) {
        return results[end] - results[start] + 1;
    }
    return results[end] - results[start];
}

int main(void) {
    prepare_table();
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", prime_count(a, b));
    }
    return 0;
}
